Ví dụ Thuật_toán_Edmonds–Karp

Xét một mạng gồm bảy đỉnh, đỉnh phát A, đỉnh thu G, và khả năng thông qua được cho trong hình dưới đây:

Trong cặp số f / c {\displaystyle f/c} trên mỗi cung, f {\displaystyle f} là luồng hiện tại, và c {\displaystyle c} khả năng thông qua. Khả năng thông qua còn dư từ u {\displaystyle u} đến v {\displaystyle v} là c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} , hiệu của khả năng thông qua và luồng hiện tại. Nếu luồng từ u {\displaystyle u} đến v {\displaystyle v} là âm, nó làm tăng khả năng thông qua còn dư từ u {\displaystyle u} đến v {\displaystyle v} .

Khả năng thông quaĐường
Mạng thu được
min ( c f ( A , D ) , c f ( D , E ) , c f ( E , G ) ) = {\displaystyle \min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=}

min ( 3 − 0 , 2 − 0 , 1 − 0 ) = {\displaystyle \min(3-0,2-0,1-0)=}
min ( 3 , 2 , 1 ) = 1 {\displaystyle \min(3,2,1)=1}

A , D , E , G {\displaystyle A,D,E,G}
min ( c f ( A , D ) , c f ( D , F ) , c f ( F , G ) ) = {\displaystyle \min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=}

min ( 3 − 1 , 6 − 0 , 9 − 0 ) = {\displaystyle \min(3-1,6-0,9-0)=}
min ( 2 , 6 , 9 ) = 2 {\displaystyle \min(2,6,9)=2}

A , D , F , G {\displaystyle A,D,F,G}
min ( c f ( A , B ) , c f ( B , C ) , c f ( C , D ) , c f ( D , F ) , c f ( F , G ) ) = {\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=}

min ( 3 − 0 , 4 − 0 , 1 − 0 , 6 − 2 , 9 − 2 ) = {\displaystyle \min(3-0,4-0,1-0,6-2,9-2)=}
min ( 3 , 4 , 1 , 4 , 7 ) = 1 {\displaystyle \min(3,4,1,4,7)=1}

A , B , C , D , F , G {\displaystyle A,B,C,D,F,G}
min ( c f ( A , B ) , c f ( B , C ) , c f ( C , E ) , c f ( E , D ) , c f ( D , F ) , c f ( F , G ) ) = {\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))=}

min ( 3 − 1 , 4 − 1 , 2 − 0 , 0 − − 1 , 6 − 3 , 9 − 3 ) = {\displaystyle \min(3-1,4-1,2-0,0--1,6-3,9-3)=}
min ( 2 , 3 , 2 , 1 , 3 , 6 ) = 1 {\displaystyle \min(2,3,2,1,3,6)=1}

A , B , C , E , D , F , G {\displaystyle A,B,C,E,D,F,G}

Chú ý là chiều dài đường tăng luồng (màu đỏ) không bao giờ giảm. Đường tăng tìm được luôn là ngắn nhất có thể. Luồng tìm được bằng tổng khả năng thông qua của lát cắt cực tiểu trong đồ thị chia cắt đỉnh phát và đỉnh thu. Có đúng một lát cắt nhỏ nhất trong đồ thị này, chia tập hợp đỉnh thành { A , B , C , E } {\displaystyle \{A,B,C,E\}} và { D , F , G } {\displaystyle \{D,F,G\}} , và có khả năng thông qua

c ( A , D ) + c ( C , D ) + c ( E , G ) = 3 + 1 + 1 = 5.   {\displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\ }